package com.liang.bishi.wy;

import java.util.*;

/**
 * 第二题：BFS 求最短路径
 * 题目：城市有 n 个公交站点（0 到 n-1）和 m 辆公交车，每辆车在区间 a-b 内运行，乘客可以在区间内的任意站点上下车进行换乘
 * 小明从 x 站点到 y 站点，求至少需要乘坐几趟公交车。如果无法到达返回 -1，若起点和终点相同则返回 0。
 * <p>
 * 5 3
 * 0 4
 * 0 2
 * 1 3
 * 3 4
 * <p>
 * 3
 */
public class Problem2 {

    // 定义公交车区间
    static class Bus {
        int start, end;

        Bus(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 输入站点数n和公交车数m
        int n = sc.nextInt();
        int m = sc.nextInt();

        // 输入起点x和终点y
        int x = sc.nextInt();
        int y = sc.nextInt();

        // 如果起点和终点相同，直接输出0
        if (x == y) {
            System.out.println(0);
            return;
        }

        // 输入每辆公交车的区间
        List<Bus> buses = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            buses.add(new Bus(a, b));
        }

        // 建立公交车之间的换乘图，graph[i] 存储公交车i可以换乘的公交车
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            graph.add(new ArrayList<>());
        }

        // 建立公交车之间的换乘关系
        for (int i = 0; i < m; i++) {
            for (int j = i + 1; j < m; j++) {
                if (hasOverlap(buses.get(i), buses.get(j))) {
                    graph.get(i).add(j);
                    graph.get(j).add(i);
                }
            }
        }

        // 寻找哪些公交车区间包含起点x和终点y
        List<Integer> startBuses = new ArrayList<>();
        List<Integer> endBuses = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            if (x >= buses.get(i).start && x <= buses.get(i).end) {
                startBuses.add(i);
            }
            if (y >= buses.get(i).start && y <= buses.get(i).end) {
                endBuses.add(i);
            }
        }

        // 使用BFS计算最小的换乘次数
        int result = bfs(startBuses, endBuses, graph, m);
        System.out.println(result);
    }

    // 判断两个公交车区间是否有重叠
    private static boolean hasOverlap(Bus bus1, Bus bus2) {
        return bus1.end >= bus2.start && bus2.end >= bus1.start;
    }

    // BFS计算最小换乘次数
    private static int bfs(List<Integer> startBuses, List<Integer> endBuses, List<List<Integer>> graph, int m) {
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[m];

        // 初始化起始公交车队列
        for (int bus : startBuses) {
            queue.offer(bus);
            visited[bus] = true;
        }

        int transfers = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            transfers++;
            for (int i = 0; i < size; i++) {
                int currentBus = queue.poll();

                // 如果当前公交车是到达终点的公交车之一，返回换乘次数
                if (endBuses.contains(currentBus)) {
                    return transfers;
                }

                // 遍历当前公交车可以换乘的公交车
                for (int nextBus : graph.get(currentBus)) {
                    if (!visited[nextBus]) {
                        visited[nextBus] = true;
                        queue.offer(nextBus);
                    }
                }
            }
        }

        // 无法到达终点
        return -1;
    }
}

